Directory assistance (DA) services, sometimes referred to as 411 services, enable users to find out the phone number associated with a business or residential listing. Currently, DA services are becoming increasingly popular. A typical automatic DA system includes a recognition component configured to determine a query based on input from a user. The system then produces a ranked set of listings that correspond to the query.
To accurately search for a listing, it is often helpful to incorporate as much information as possible into the analysis of determining the contents of the ranked set of listings. For example, a DA system wherein the recognition component is a speech recognizer might be configured to determine the ranked set based on information other than simply just a recognized utterance. Examples of other types of information that might be accounted for include listing categories and static ranking. Regardless of which multiple parameters are accounted for, to produce the ranked set of listings, many systems will calculate some form of a combined score for a large set of potentially matching listings.
Some recognition-based (e.g., as opposed to text-based) DA services are configured to collect multiple items of information from the user. For example, some systems will conduct several dialog turns to ask for city names, listing names, and sometimes disambiguation. The DA system searches for matching listings based on recognized text. It is possible that the user input, as recognized, may contain errors. For at least this reason, a specialized searching and ranking algorithm configured to account for the possibility of errors is utilized. Typical searching algorithms include TF*IDF (term frequency-inverse document frequency) and MaxEnt (maximum entropy). Regardless of the algorithm utilized, the scoring can typically be converted to:
                              s          ⁡                      (                                          l                i                            ❘                                                f                  j                                ⁡                                  (                                                            l                      i                                        ,                    u                                    )                                                      )                          =                              ∑            j                    ⁢                                    λ                              i                ,                j                                      ⁢                                          f                j                            ⁡                              (                                                      l                    i                                    ,                  u                                )                                                                        (        1        )            
Here, λi,j are non-negative scores and fj are features, for example, common words in the utterance and the listing, category of the listing, estimated category from the utterance, and the static score of the listing. New features can be added when available. It should be noted that li can be a listing or something else (e.g., a category) if the user's utterance does not contain enough information for a listing.
In accordance with equation (1), to search for a correct listing, a system generally must calculate a score for each listing li. One or more (e.g., the top N) of the highest scoring listings are selected as being the most likely accurate search result or results. It would be desirable to implement an alternative algorithm that would enable a system to rank potentially matching listings in a more efficient manner.
The discussion above is merely provided for general background information and is not intended for use as an aid in determining the scope of the claimed subject matter.